{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #魔塔游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: magicTower"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #魔塔游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "小扣当前位于魔塔游戏第一层，共有 `N` 个房间，编号为 `0 ~ N-1`。每个房间的补血道具/怪物对于血量影响记于数组 `nums`，其中正数表示道具补血数值，即血量增加对应数值；负数表示怪物造成伤害值，即血量减少对应数值；`0` 表示房间对血量无影响。\n",
    "\n",
    "**小扣初始血量为 1，且无上限**。假定小扣原计划按房间编号升序访问所有房间补血/打怪，**为保证血量始终为正值**，小扣需对房间访问顺序进行调整，**每次仅能将一个怪物房间（负数的房间）调整至访问顺序末尾**。请返回小扣最少需要调整几次，才能顺利访问所有房间。若调整顺序也无法访问完全部房间，请返回 -1。\n",
    "\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`nums = [100,100,100,-250,-60,-140,-50,-50,100,150]`\n",
    ">\n",
    ">输出：`1`\n",
    ">\n",
    ">解释：初始血量为 1。至少需要将 nums[3] 调整至访问顺序末尾以满足要求。\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`nums = [-200,-300,400,0]`\n",
    ">\n",
    ">输出：`-1`\n",
    ">\n",
    ">解释：调整访问顺序也无法完成全部房间的访问。\n",
    "\n",
    "**提示：**\n",
    "- `1 <= nums.length <= 10^5`\n",
    "- `-10^5 <= nums[i] <= 10^5`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [p0NxJO](https://leetcode.cn/problems/p0NxJO/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [p0NxJO](https://leetcode.cn/problems/p0NxJO/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[100,100,100,-250,-60,-140,-50,-50,100,150]', '[-200,-300,400,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        q = deque(nums)\n",
    "        monster = []\n",
    "        i = 0\n",
    "        hp = 0\n",
    "        cnt = 0\n",
    "        while(i < len(q)):\n",
    "            hp = hp + q[i]\n",
    "            if q[i] < 0:\n",
    "                heappush(monster, q[i])\n",
    "            if hp < 0:\n",
    "                top = heappop(monster)\n",
    "                q.append(top)\n",
    "                hp -= top\n",
    "                cnt += 1\n",
    "            i += 1\n",
    "        return cnt\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if 1 + sum(nums) <= 0:\n",
    "            return -1\n",
    "        hp = 1\n",
    "        ans = 0\n",
    "        down = []\n",
    "        for i in nums:\n",
    "            if i < 0:\n",
    "                down.append(i)\n",
    "                hp_n = hp + i\n",
    "                if hp_n <= 0:\n",
    "                    back = down.pop(down.index(min(down)))\n",
    "                    hp -= back\n",
    "                    ans += 1\n",
    "            hp += i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        s = sum(nums)\n",
    "        if s < -1: return -1\n",
    "        h = []\n",
    "        cur = 1\n",
    "        ans = 0\n",
    "        q = deque(nums)\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            if x > 0: cur += x\n",
    "            if x < 0: \n",
    "                if cur + x > 0:\n",
    "                    cur += x\n",
    "                    heappush(h, x)\n",
    "                else:\n",
    "                    if h and x > h[0]:\n",
    "                        cur = cur - h[0] + x\n",
    "                        q.append(heapreplace(h, x))\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        ans += 1\n",
    "                        q.append(x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "\n",
    "        hp = 1\n",
    "        cnt = 0\n",
    "        temp = []\n",
    "        heapify(temp)\n",
    "        for cur in nums:             \n",
    "            hp += cur\n",
    "            if cur < 0:\n",
    "                heappush(temp,cur)\n",
    "                while hp <= 0:\n",
    "                    monster = heappop(temp)\n",
    "                    #nums.append(monster)\n",
    "                    cnt += 1\n",
    "                    hp -= monster\n",
    "        \n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums)<0:\n",
    "            return -1\n",
    "\n",
    "        summ = 0\n",
    "        zhai = []\n",
    "        ans = 0\n",
    "\n",
    "        for i in nums:\n",
    "            if i >= 0:\n",
    "                summ += i\n",
    "            else:\n",
    "                if summ+i>= 0:\n",
    "                    summ += i\n",
    "                    zhai.append(i)\n",
    "                else:\n",
    "                    zhai.append(i)\n",
    "                    zhai.sort(key=lambda x:-x)\n",
    "                    ans += 1\n",
    "                    summ -= zhai.pop()\n",
    "                    summ += i\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        # res = final_harm = 0\n",
    "        # harm_heap = []\n",
    "        # blood = 1\n",
    "        # for i in nums:\n",
    "        #     if i < 0:\n",
    "        #         heappush(harm_heap, i)\n",
    "        #         if blood + i <= 0:\n",
    "        #             if harm_heap:\n",
    "        #                 blood += i - harm_heap[0]\n",
    "        #                 if blood <= 0:\n",
    "        #                     return -1\n",
    "        #                 final_harm += heappop(harm_heap)\n",
    "        #             res += 1\n",
    "        #         else:\n",
    "        #             blood += i\n",
    "        #     else:\n",
    "        #         blood += i \n",
    "        # return res if blood + final_harm > 0 else -1\n",
    "\n",
    "        # -----------------------------\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        harm_heap = []\n",
    "        res = blood = 0\n",
    "        for i in nums:\n",
    "            blood += i \n",
    "            if i < 0:\n",
    "                heappush(harm_heap, i)\n",
    "            if blood < 0:\n",
    "                res += 1\n",
    "                blood -= heappop(harm_heap)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        hp = 1\n",
    "        count = 0\n",
    "        arr = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < 0:\n",
    "                arr.append(nums[i])\n",
    "            hp += nums[i]\n",
    "            if hp <= 0:\n",
    "                m = min(arr)\n",
    "                hp -= m\n",
    "                arr.remove(m)\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        hurts = []\n",
    "        blood = 0\n",
    "        counts = 0 \n",
    "        heapify(hurts)\n",
    "        for i in nums:\n",
    "            blood += i\n",
    "            if i < 0:\n",
    "                heapq.heappush(hurts, i)\n",
    "            if blood < 0:\n",
    "                counts += 1\n",
    "                blood -= heappop(hurts)\n",
    "        return counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        # 负数进堆， 小顶堆， 往后遍历， 通不过去时把最小的负数丢后面去。\n",
    "        # 则当前血量要加回减去的这个负数\n",
    "        # 然后往后遍历\n",
    "        # cur = 1\n",
    "        # hq = []\n",
    "        # # cnt = 0\n",
    "        # n = len(nums)\n",
    "\n",
    "        # pop_list = []\n",
    "        # for x in nums:\n",
    "        #     if x >= 0:\n",
    "        #         cur += x\n",
    "        #     elif x < 0:\n",
    "        #         while cur + x < 0:\n",
    "        #             if hq:\n",
    "        #                 tm = heappop(hq)\n",
    "        #                 cur -= tm\n",
    "        #                 pop_list.append(tm)\n",
    "        #                 # cnt += 1\n",
    "        #             else:\n",
    "        #                 heapq.heappush(hq, x)\n",
    "        #                 continue\n",
    "        #         heapq.heappush(hq, x)\n",
    "        #         cur += x\n",
    "        # if cur + sum(hq):\n",
    "        #     return len(hq)\n",
    "        # else:\n",
    "        #     return -1\n",
    "        \n",
    "\n",
    "\n",
    "        # 清风\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "\n",
    "        hurts = []\n",
    "        blood = 0\n",
    "        cnt = 0\n",
    "        heapq.heapify(hurts)\n",
    "        for x in nums:\n",
    "            blood += x\n",
    "            if x < 0:\n",
    "                heapq.heappush(hurts, x)\n",
    "            if blood < 0:\n",
    "                cnt += 1\n",
    "                blood -= heapq.heappop(hurts)\n",
    "        return cnt\n",
    "\n",
    "        \n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        res = final_harm = 0\n",
    "        harm_heap = []\n",
    "        blood = 1\n",
    "        for i in nums:\n",
    "            if i < 0:\n",
    "                heappush(harm_heap, i)\n",
    "                if blood + i <= 0:\n",
    "                    if harm_heap:\n",
    "                        blood += i - harm_heap[0]\n",
    "                        if blood <= 0:\n",
    "                            return -1\n",
    "                        final_harm += heappop(harm_heap)\n",
    "                    res += 1\n",
    "                else:\n",
    "                    blood += i\n",
    "            else:\n",
    "                blood += i \n",
    "        return res if blood + final_harm > 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        s, ret = 1, 0\n",
    "        Q = []\n",
    "        for i, x in enumerate(nums):\n",
    "            s += x\n",
    "            if x < 0:\n",
    "                heappush(Q, x)\n",
    "            while s <= 0:\n",
    "                ret += 1\n",
    "                t = heappop(Q)\n",
    "                s = s - t\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0: return -1\n",
    "        total = 0\n",
    "        res = 0\n",
    "        h = []\n",
    "        for i, x in enumerate(nums):\n",
    "            if x < 0: heappush(h, x)\n",
    "            total += x \n",
    "            if total < 0:\n",
    "                res += 1\n",
    "                total -= h[0]\n",
    "                heappop(h)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0 :\n",
    "            return -1\n",
    "        ans,blood ,q=0,1,[]\n",
    "\n",
    "        for num in nums:\n",
    "            if num < 0 :\n",
    "                heappush(q,num)\n",
    "            blood +=num\n",
    "            if blood <= 0:\n",
    "                blood -= heappop(q)\n",
    "                ans+=1\n",
    "\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        Monster = []\n",
    "        idx, blood_volume, ans = 0, 0, 0\n",
    "        while idx < len(nums):\n",
    "            if nums[idx] < 0:\n",
    "                heappush(Monster, nums[idx])\n",
    "            blood_volume += nums[idx]\n",
    "            if blood_volume < 0:\n",
    "                blood_volume += -heappop(Monster)\n",
    "                ans += 1\n",
    "            idx += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            if nums[0] > 0:\n",
    "                return 0\n",
    "            return -1\n",
    "\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "\n",
    "        heap = []\n",
    "        hp = 1\n",
    "        num_defer = 0\n",
    "        for x in nums:\n",
    "            if x < 0:\n",
    "                heapq.heappush(heap, x)\n",
    "\n",
    "            hp += x\n",
    "\n",
    "            while hp <= 0:\n",
    "                defer = heapq.heappop(heap)\n",
    "                hp -= defer\n",
    "                num_defer += 1\n",
    "\n",
    "        return num_defer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        blood = 1\n",
    "        remain = 0\n",
    "        c = 0\n",
    "        q = []\n",
    "        for b in nums:\n",
    "            if b >= 0:\n",
    "                blood += b\n",
    "            else:\n",
    "                heapq.heappush(q, b)\n",
    "                blood += b\n",
    "                while blood <= 0 < len(q):\n",
    "                    b = heapq.heappop(q)\n",
    "                    blood -= b\n",
    "                    c += 1\n",
    "                    remain += b\n",
    "                if blood < 0:\n",
    "                    return -1\n",
    "        if blood + remain <= 0:\n",
    "            return -1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "      if sum(nums) < 0:\n",
    "        return -1\n",
    "      s = 0\n",
    "      res = 0\n",
    "      h = []\n",
    "      for n in nums:\n",
    "        s += n\n",
    "        if n < 0:\n",
    "          heapq.heappush(h,n)\n",
    "        if s < 0:\n",
    "          s -= heapq.heappop(h)\n",
    "          res += 1\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        cur = 1 \n",
    "        res = 0 \n",
    "        pq = []\n",
    "        for x in nums:\n",
    "            heappush(pq, x)\n",
    "            cur += x \n",
    "            while cur <= 0:\n",
    "                res += 1\n",
    "                cur -= heappop(pq)\n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if(1 + sum(nums) < 0):\n",
    "            return -1\n",
    "        heap = []\n",
    "        hp = 1\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            hp += nums[i]\n",
    "            if(nums[i] < 0):\n",
    "                heapq.heappush(heap, nums[i])\n",
    "            while(heap and hp <= 0):\n",
    "                h = heapq.heappop(heap)\n",
    "                hp -= h \n",
    "                result += 1\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        axx = []\n",
    "        sum = 1\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            sum += i\n",
    "        if sum < 1:\n",
    "            return -1\n",
    "        sum = 1\n",
    "        for i in nums:\n",
    "            if i < 0:\n",
    "                axx.append(i* -1)\n",
    "            if sum < 1:\n",
    "                while sum < 1:\n",
    "                    sum += max(axx)\n",
    "                    axx.remove(max(axx))\n",
    "                    count += 1\n",
    "            sum += i\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cur_sum =0 \n",
    "        time = 0\n",
    "        min_sum = 0\n",
    "        min_heap = []\n",
    "        for i in range(n):\n",
    "            cur_sum += nums[i]\n",
    "            if nums[i]<0:\n",
    "                heapq.heappush(min_heap,nums[i])\n",
    "            if cur_sum<0:\n",
    "                 cur_min = heapq.heappop(min_heap)\n",
    "                 min_sum  -= cur_min\n",
    "                 cur_sum-=cur_min\n",
    "                 time+=1\n",
    "        if cur_sum<min_sum: return -1 \n",
    "        return time \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        total = sum(nums)\n",
    "        if total < 0:\n",
    "            return -1\n",
    "        cnt = 0\n",
    "        total = 0\n",
    "        walk = []\n",
    "        for i in range(len(nums)):\n",
    "            total += nums[i]\n",
    "            walk.append(nums[i])\n",
    "            while total < 0:\n",
    "                tmp = min(walk)\n",
    "                walk.remove(tmp)\n",
    "                total -= tmp\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 先依次加减, 负数时加入数组 q 中 \n",
    "# 当无法进行下一步时, 将 q 中最大的负数取出放入 wait 数组中\n",
    "# 如果可以遍历完毕, 那么与 wait 数组和相加, 正数则输出 wait 数组长度, 否则输出 -1\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if 1 + sum(nums) <= 0:\n",
    "            return -1\n",
    "            \n",
    "        wait = []   # 需要调整的关卡\n",
    "        q = []\n",
    "\n",
    "        hp = 1\n",
    "        for digit in nums:\n",
    "            hp += digit\n",
    "            if digit < 0:\n",
    "                heappush(q, digit)  # 最小堆第一个为最小的负数\n",
    "                if hp <= 0:\n",
    "                    p = heappop(q)\n",
    "                    hp = hp - p\n",
    "                    wait.append(p)\n",
    "        \n",
    "        return len(wait) if hp + sum(wait) > 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        monster = []\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        hp = 0\n",
    "        cnt = 0\n",
    "        while(i < n):\n",
    "            hp = hp + nums[i]\n",
    "            if nums[i] < 0:\n",
    "                heappush(monster, nums[i])\n",
    "            if hp < 0:\n",
    "                top = heappop(monster)\n",
    "                hp -= top\n",
    "                cnt += 1\n",
    "            i += 1\n",
    "        return cnt\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        total_sum = sum(nums)\n",
    "        # If total sum is still negative even after visiting all rooms, return -1\n",
    "        if total_sum < 0:\n",
    "            return -1\n",
    "        \n",
    "        health = 1  # Initial health\n",
    "        adjustments = 0  # Number of adjustments needed\n",
    "        min_heap = []  # Min heap to keep track of the monsters\n",
    "        \n",
    "        for num in nums:\n",
    "            health += num  # Update health after visiting the room\n",
    "            \n",
    "            # If it's a monster room, add its damage to the min_heap\n",
    "            if num < 0:\n",
    "                heapq.heappush(min_heap, num)\n",
    "            \n",
    "            # While health is not positive, move the least damaging monster to the end\n",
    "            while health <= 0:\n",
    "                health -= heapq.heappop(min_heap)  # Remove the least damaging monster and add its damage back to health\n",
    "                adjustments += 1  # Increment the number of adjustments\n",
    "                \n",
    "        return adjustments\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        heap = []\n",
    "        hp = ans = 0\n",
    "        for num in nums:\n",
    "            heappush(heap, num)\n",
    "            hp += num\n",
    "            if hp < 0:\n",
    "                hp -= heappop(heap)\n",
    "                ans += 1\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if(1 + sum(nums) < 0):\n",
    "            return -1\n",
    "        heap = []\n",
    "        hp = 1\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            hp += nums[i]\n",
    "            if(nums[i] < 0):\n",
    "                heapq.heappush(heap, nums[i])\n",
    "            while(heap and hp <= 0):\n",
    "                h = heapq.heappop(heap)\n",
    "                hp -= h \n",
    "                result += 1\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums)<0:\n",
    "            return -1\n",
    "        reduce=[]\n",
    "        now=1\n",
    "        c=0\n",
    "        for n in nums:\n",
    "            now=now+n\n",
    "            heapq.heappush(reduce,n)\n",
    "            if now <=0:\n",
    "                now-=heapq.heappop(reduce)\n",
    "                c+=1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "\n",
    "        b = 1\n",
    "        h = []\n",
    "        rst = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if num >= 0:\n",
    "                b += num\n",
    "            else:\n",
    "                heapq.heappush(h, num)\n",
    "                if b + num <= 0:\n",
    "                    b += -heapq.heappop(h)\n",
    "                    b += num\n",
    "                    rst += 1\n",
    "                else:\n",
    "                    b += num\n",
    "\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        total = 1\n",
    "        res = []\n",
    "        heapq.heapify(res)\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            if i < 0:\n",
    "                heapq.heappush(res,i)\n",
    "            total += i\n",
    "            while total <= 0:\n",
    "                temp = heapq.heappop(res)\n",
    "                total -= temp\n",
    "                count += 1\n",
    "        return count\n",
    "\n",
    "        # 最小堆.\n",
    "        # 如果数组和小于零,则返回-1.\n",
    "        #遍历数组,把负数用最小堆管理,如果总和total小于1,则从最小堆中取出最小的数."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums)<0:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        q = []\n",
    "        ans = 0\n",
    "        cur = 1\n",
    "        for x in nums:\n",
    "            if x<0:\n",
    "                heappush(q,x)\n",
    "                if cur+x<=0:\n",
    "                    guai = heappop(q)\n",
    "                    ans += 1\n",
    "                    cur -= guai\n",
    "            cur += x\n",
    "            \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:return -1\n",
    "\n",
    "        h = []\n",
    "        ans = 0\n",
    "        cur = 1\n",
    "        for num in nums:\n",
    "            if num < 0:\n",
    "                heappush(h, num)\n",
    "            cur += num\n",
    "            while cur <= 0:\n",
    "                ans += 1\n",
    "                cur += abs(heappop(h))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums)+1<0:\n",
    "            return -1\n",
    "        cnt = 0\n",
    "        queue = []\n",
    "        leave = []\n",
    "        for num in nums:\n",
    "            cnt+=num\n",
    "            if num<0:\n",
    "                heapq.heappush(queue,num)\n",
    "            if cnt<0:\n",
    "                a = heapq.heappop(queue)\n",
    "                cnt -= a\n",
    "                leave.append(a)\n",
    "        return len(leave)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if(1 + sum(nums) < 0):\n",
    "            return -1\n",
    "        heap = []\n",
    "        hp = 1\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            hp += nums[i]\n",
    "            if(nums[i] < 0):\n",
    "                heapq.heappush(heap, nums[i])\n",
    "            while(heap and hp <= 0):\n",
    "                h = heapq.heappop(heap)\n",
    "                hp -= h \n",
    "                result += 1\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        #小顶堆\n",
    "        q=[]\n",
    "        ans=0\n",
    "        cur=1\n",
    "        if sum(nums)<0:\n",
    "            return -1\n",
    "        for x in nums:\n",
    "            if x >= 0:\n",
    "                cur += x\n",
    "            else:\n",
    "                cur += x\n",
    "                heappush(q,x)\n",
    "                if cur <= 0:\n",
    "                    cur -= heappop(q)\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        heap=[]\n",
    "        cur=1\n",
    "        n=len(nums)\n",
    "        k=0\n",
    "        for i in range(n):\n",
    "            cur=cur+nums[i]\n",
    "            heappush(heap,nums[i])\n",
    "            while heap and cur<1:\n",
    "                cur-=heappop(heap)\n",
    "                k+=1\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        import heapq as hq\n",
    "        q=[]\n",
    "        hp=1\n",
    "        res=0\n",
    "        if sum(nums)<0: return -1\n",
    "        for c in nums:\n",
    "            hp+=c\n",
    "            if c<0:\n",
    "                hq.heappush(q,c)\n",
    "            if hp<=0:\n",
    "                res+=1\n",
    "                minc = hq.heappop(q)\n",
    "                hp-=minc\n",
    "        return res\n",
    "\n",
    "    def magicTower_e0(self, nums: List[int]) -> int:\n",
    "        idx=0\n",
    "        hp=1\n",
    "        n=len(nums)\n",
    "        res=0\n",
    "        loop=n+1\n",
    "        while loop:\n",
    "            loop-=1\n",
    "            while idx<n and hp+nums[idx]>0:\n",
    "                hp+=nums[idx]\n",
    "                idx+=1\n",
    "                print('hp inc :',hp,idx,n)\n",
    "            \n",
    "            if idx==n:\n",
    "                return res\n",
    "            else:\n",
    "                # loop+=1\n",
    "                min_neg=0\n",
    "                idx0=idx\n",
    "                while idx>=0 and nums[idx]<0:\n",
    "                    min_neg=min(min_neg,nums[idx])\n",
    "                    idx-=1\n",
    "                    if idx>=0 and nums[idx]<0:\n",
    "                        hp-=nums[idx]\n",
    "                # loop+=(idx0-idx)\n",
    "                print(min_neg, idx)\n",
    "                nums.append(min_neg)\n",
    "                n+=1\n",
    "                idx+=1\n",
    "                nums[idx]=0\n",
    "                print(nums,idx)\n",
    "                res+=1\n",
    "        print('end')\n",
    "        return res if idx==n else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums)+1<0:\n",
    "            return -1\n",
    "        cnt = 1\n",
    "        queue = []\n",
    "        leave = []\n",
    "        for num in nums:\n",
    "            cnt+=num\n",
    "            if num<0:\n",
    "                heapq.heappush(queue,num)\n",
    "            if cnt<=0:\n",
    "                a = heapq.heappop(queue)\n",
    "                cnt -= a\n",
    "                leave.append(a)\n",
    "        return len(leave)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        total = sum(nums)\n",
    "        if total < 0:\n",
    "            return -1\n",
    "        cnt = 0\n",
    "        total = 0\n",
    "        walk = []\n",
    "        for i in range(len(nums)):\n",
    "            total += nums[i]\n",
    "            # 记录访问过的房间血量\n",
    "            walk.append(nums[i])\n",
    "            # 回溯\n",
    "            while total < 0:\n",
    "                tmp = min(walk)\n",
    "                # 因为调整了访问顺序，故移除该房间的血量记录\n",
    "                walk.remove(tmp)\n",
    "                total -= tmp\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        ans = 0\n",
    "        q = []\n",
    "        s = 1\n",
    "        for i in nums:\n",
    "            s += i\n",
    "            if i >= 0:\n",
    "                continue\n",
    "            else:\n",
    "                heappush(q,i)\n",
    "                if s <= 0:\n",
    "                    s += -heappop(q)\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        blood = 1\n",
    "        queue = []\n",
    "        res = []\n",
    "        for num in nums:\n",
    "            if num < 0:\n",
    "                if blood + num <= 0:\n",
    "                    if queue and queue[0] < num:\n",
    "                        blood += num - queue[0]\n",
    "                        res.append(queue[0])\n",
    "                        heappop(queue)\n",
    "                        heappush(queue, num)\n",
    "                    else:\n",
    "                        res.append(num)\n",
    "                else:\n",
    "                    heappush(queue, num)\n",
    "                    blood += num\n",
    "            else:\n",
    "                blood += num\n",
    "        return len(res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        import heapq\n",
    "\n",
    "        ans = 0\n",
    "        negs = []\n",
    "        q = []\n",
    "        heapq.heapify(q)\n",
    "        cum_sum = 1\n",
    "        for num in nums:\n",
    "            if num < 0:\n",
    "                heapq.heappush(q, num)\n",
    "\n",
    "            cum_sum += num\n",
    "            while cum_sum < 1:\n",
    "                neg = heapq.heappop(q)\n",
    "                negs.append(neg)\n",
    "                ans += 1\n",
    "                cum_sum -= neg\n",
    "        \n",
    "        sum_neg = sum(negs)\n",
    "        return ans if sum_neg + cum_sum >= 1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "\n",
    "        if sum(nums)<0:return -1\n",
    "        s=1\n",
    "        heap=[]\n",
    "        res=0\n",
    "        for v in nums:\n",
    "            s+=v\n",
    "            heappush(heap,v)\n",
    "            while s<=0:\n",
    "                s-=heappop(heap)\n",
    "                res+=1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        cur = 1\n",
    "        hp = []\n",
    "        select = []\n",
    "        for x in nums:\n",
    "            if x<0:\n",
    "                heappush(hp, x)\n",
    "            cur +=x\n",
    "            while cur<=0:\n",
    "                if len(hp)==0:\n",
    "                    return -1\n",
    "                select.append(heappop(hp))\n",
    "                cur -= select[-1]\n",
    "        return len(select) if cur+sum(select)>0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        total = 1\n",
    "        res = []\n",
    "        heapq.heapify(res)\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            if i < 0:\n",
    "                heapq.heappush(res,i)\n",
    "            total += i\n",
    "            while total <= 0:\n",
    "                temp = heapq.heappop(res)\n",
    "                total -= temp\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def magicTower(self, nums: List[int]) -> int:\r\n",
    "        if sum(nums) < 0: \r\n",
    "            return -1\r\n",
    "        hurts = []\r\n",
    "        blood = 0\r\n",
    "        counts = 0\r\n",
    "        heapq.heapify(hurts)\r\n",
    "        for i in nums:\r\n",
    "            blood += i\r\n",
    "            if i < 0:\r\n",
    "                heapq.heappush(hurts, i)   \r\n",
    "            if blood < 0:\r\n",
    "                counts += 1\r\n",
    "                blood -= heapq.heappop(hurts)\r\n",
    "        return counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if(1 + sum(nums) < 0):\n",
    "            return -1\n",
    "        heap = []\n",
    "        hp = 1\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            hp += nums[i]\n",
    "            if(nums[i] < 0):\n",
    "                heapq.heappush(heap, nums[i])\n",
    "            while(heap and hp <= 0):\n",
    "                h = heapq.heappop(heap)\n",
    "                hp -= h \n",
    "                result += 1\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        premonster = []\n",
    "        res = 0\n",
    "        pre = 1\n",
    "        move = 0\n",
    "        for num in nums:\n",
    "            cur = pre+num\n",
    "            if num < 0:\n",
    "                heapq.heappush(premonster, num)\n",
    "            while cur <= 0 and premonster:\n",
    "                tmp = heapq.heappop(premonster)\n",
    "                cur -= tmp\n",
    "                res += 1\n",
    "                move -= tmp\n",
    "            if cur < 0:\n",
    "                return -1\n",
    "        \n",
    "            pre = cur\n",
    "        if pre >= move: return res\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        ans = 0\n",
    "        h = []\n",
    "        s = 1\n",
    "        for x in nums:\n",
    "            s += x\n",
    "            if s < 1:                           \n",
    "                if h and x > h[0]:\n",
    "                    s -= heappop(h)    \n",
    "                    heappush(h, x)                \n",
    "                    ans += 1\n",
    "                else:\n",
    "                    s -= x\n",
    "                    ans += 1\n",
    "            else:\n",
    "                if x < 0:\n",
    "                    heappush(h, x)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        # # plan1:\n",
    "        # if sum(nums) < 0:\n",
    "        #     return -1\n",
    "        # cnt = 0\n",
    "        # total = 0\n",
    "        # walk = []\n",
    "        # for i in range(len(nums)):\n",
    "        #     total += nums[i]\n",
    "        #     walk.append(nums[i])\n",
    "        #     while total < 0:\n",
    "        #         tmp = min(walk)\n",
    "        #         walk.remove(tmp)\n",
    "        #         total -= tmp\n",
    "        #         cnt += 1\n",
    "        # return cnt\n",
    "\n",
    "        # plan2:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cur_sum = 0\n",
    "        time = 0\n",
    "        minHeap = []\n",
    "        for i in range(n):\n",
    "            cur_sum += nums[i]\n",
    "            if nums[i] < 0:\n",
    "                heapq.heappush(minHeap, nums[i])\n",
    "            if cur_sum < 0:\n",
    "                cur_min = heapq.heappop(minHeap)\n",
    "                cur_sum -= cur_min\n",
    "                time += 1\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        cnt = 0\n",
    "        total = 0\n",
    "        walk = []\n",
    "        for i in range(len(nums)):\n",
    "            total += nums[i]\n",
    "            walk.append(nums[i])\n",
    "            while total < 0:\n",
    "                tmp = min(walk)\n",
    "                walk.remove(tmp)\n",
    "                total -= tmp\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        \n",
    "        cur = 1\n",
    "        ans = 0\n",
    "        hq = []\n",
    "        for num in nums:\n",
    "            if num < 0:\n",
    "                heapq.heappush(hq, num)\n",
    "\n",
    "            ## 如果进入当前房间我就会死，那么必须要考虑之前经过的扣血的房间，把他们移到最后我才能活\n",
    "            if cur + num <= 0:\n",
    "                if hq:\n",
    "                    ans += 1\n",
    "                    cur += -heapq.heappop(hq)\n",
    "            if cur + num > 0:\n",
    "                cur += num\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        total = sum(nums)\n",
    "        if total < 0:\n",
    "            return -1\n",
    "        cnt = 0\n",
    "        total = 0\n",
    "        walk = []\n",
    "        for i in range(len(nums)):\n",
    "            total += nums[i]\n",
    "            # 记录访问过的房间血量\n",
    "            walk.append(nums[i])\n",
    "            # 回溯\n",
    "            while total < 0:\n",
    "                tmp = min(walk)\n",
    "                # 因为调整了访问顺序，故移除该房间的血量记录\n",
    "                walk.remove(tmp)\n",
    "                total -= tmp\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def magicTower(self, nums: list[int]) -> int:\n",
    "        self.nums = nums\n",
    "\n",
    "        self.dp = queue.PriorityQueue()\n",
    "        self.total = 0\n",
    "        res = self.go()\n",
    "        print(res)\n",
    "        return res\n",
    "\n",
    "    def go(self):\n",
    "        count = 0\n",
    "        countlist = []\n",
    "        for i in range(len(self.nums)):\n",
    "            num = self.nums[i]\n",
    "            self.total += num\n",
    "            if num < 0:\n",
    "                self.dp.put(num)\n",
    "            if self.total < 0:\n",
    "                num = self.dp.get()\n",
    "                self.total -= num\n",
    "                countlist.append(num)\n",
    "                count += 1\n",
    "        if self.total + sum(countlist) < 0:\n",
    "            return -1\n",
    "        else:\n",
    "            return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        health, ans = 1, 0\n",
    "        pq, tail = [], []\n",
    "        for x in nums:\n",
    "            if x < 0:  # 记录遇到过的怪物\n",
    "                heappush(pq, x)\n",
    "            health += x\n",
    "            while health < 1 and pq:  # 反悔, 将遇到过伤害最高的怪物移至末尾\n",
    "                y = heappop(pq)\n",
    "                health -= y\n",
    "                tail.append(y)\n",
    "                ans += 1\n",
    "            if health < 1:\n",
    "                return -1\n",
    "        return ans if health + sum(tail) > 0 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums)+1<=0:\n",
    "            return -1\n",
    "        now = 1\n",
    "        cnt = 0\n",
    "        pop = []\n",
    "        for i in range(len(nums)):\n",
    "            while now<=0 and len(pop):\n",
    "                now = now - heappop(pop)\n",
    "                cnt = cnt + 1\n",
    "            if now<=0:\n",
    "                return -1\n",
    "            else:\n",
    "                now = now + nums[i]\n",
    "                heappush(pop,nums[i])\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush,heappop,heapreplace\n",
    " \n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        if sum(nums) < 0:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        pq = []\n",
    "\n",
    "        cur = ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            if cur + x >= 0:\n",
    "                cur += x\n",
    "                heappush(pq,x)\n",
    "            elif len(pq) > 0 and x > pq[0]:\n",
    "                ans += 1\n",
    "                t = heapreplace(pq,x)\n",
    "                cur += x - t\n",
    "            else:\n",
    "                ans += 1\n",
    "                \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        cur_sum=0;time = 0 ;minSum = 0 \n",
    "        minHeap=[]\n",
    "        for i in range(n):\n",
    "            cur_sum+=nums[i]\n",
    "            if nums[i]<0:\n",
    "                heapq.heappush(minHeap,nums[i])\n",
    "            if cur_sum<0:\n",
    "                cur_min=heapq.heappop(minHeap)\n",
    "                minSum -= cur_min   #这些扔到后面的，眼前跳过了，在最后还是要掉血\n",
    "                cur_sum -= cur_min  #扔掉这个最小的负数。cur_sum会变大\n",
    "                time += 1           #记录往后扔的次数\n",
    "\n",
    "        if cur_sum < minSum:    #如果正值，不能够把扔到末尾的负值抵消掉\n",
    "            return -1\n",
    "        return time\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cur_sum = 0\n",
    "        times = 0\n",
    "        negatives = 0\n",
    "        minHeap=[]\n",
    "\n",
    "        for i in range(n):\n",
    "            cur_sum+=nums[i]\n",
    "            if nums[i]<0:\n",
    "                heapq.heappush(minHeap,nums[i])\n",
    "            if cur_sum<0:\n",
    "                cur_min = heapq.heappop(minHeap)\n",
    "                cur_sum -= cur_min\n",
    "                negatives -= cur_min\n",
    "                times+=1\n",
    "        if cur_sum<negatives:\n",
    "            return -1\n",
    "        return times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        cur_sum = 0         #当前和\n",
    "        time = 0            #把负数往后扔的次数\n",
    "        minSum = 0          #负数的abs值        \n",
    "        minHeap = []        #最小堆。每次把最小的负数，扔到后面去\n",
    "\n",
    "        for i in range(n):\n",
    "            cur_sum += nums[i]  #当前和\n",
    "            \n",
    "            if nums[i] < 0:     #所有的负数，都进堆\n",
    "                heapq.heappush(minHeap, nums[i])\n",
    "                \n",
    "            if cur_sum < 0:     #当前卡住了。需要把前面经历过的这些负数中，扔一个最小的到后面\n",
    "                cur_min = heapq.heappop(minHeap)\n",
    "                \n",
    "                minSum -= cur_min   #这些扔到后面的，眼前跳过了，在最后还是要掉血\n",
    "                cur_sum -= cur_min  #扔掉这个最小的负数。cur_sum会变大\n",
    "                time += 1           #记录往后扔的次数\n",
    "\n",
    "        if cur_sum < minSum:    #如果正值，不能够把扔到末尾的负值抵消掉\n",
    "            return -1\n",
    "        return time\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def magicTower(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        \r\n",
    "        cur_sum = 0         #当前和\r\n",
    "        time = 0            #把负数往后扔的次数\r\n",
    "        minSum = 0          #负数的abs值        \r\n",
    "        minHeap = []        #最小堆。每次把最小的负数，扔到后面去\r\n",
    "\r\n",
    "        for i in range(n):\r\n",
    "            cur_sum += nums[i]  #当前和\r\n",
    "            \r\n",
    "            if nums[i] < 0:     #所有的负数，都进堆\r\n",
    "                heapq.heappush(minHeap, nums[i])\r\n",
    "                \r\n",
    "            if cur_sum < 0:     #当前卡住了。需要把前面经历过的这些负数中，扔一个最小的到后面\r\n",
    "                cur_min = heapq.heappop(minHeap)\r\n",
    "                \r\n",
    "                minSum -= cur_min   #这些扔到后面的，眼前跳过了，在最后还是要掉血\r\n",
    "                cur_sum -= cur_min  #扔掉这个最小的负数。cur_sum会变大\r\n",
    "                time += 1           #记录往后扔的次数\r\n",
    "\r\n",
    "        if cur_sum < minSum:    #如果正值，不能够把扔到末尾的负值抵消掉\r\n",
    "            return -1\r\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        # # plan1:\n",
    "        # if sum(nums) < 0:\n",
    "        #     return -1\n",
    "        # cnt = 0\n",
    "        # total = 0\n",
    "        # walk = []\n",
    "        # for i in range(len(nums)):\n",
    "        #     total += nums[i]\n",
    "        #     walk.append(nums[i])\n",
    "        #     while total < 0:\n",
    "        #         tmp = min(walk)\n",
    "        #         walk.remove(tmp)\n",
    "        #         total -= tmp\n",
    "        #         cnt += 1\n",
    "        # return cnt\n",
    "\n",
    "        # plan2:\n",
    "        n = len(nums)\n",
    "        cur_sum = 0\n",
    "        time = 0\n",
    "        minSum = 0\n",
    "        minHeap = []\n",
    "        for i in range(n):\n",
    "            cur_sum += nums[i]\n",
    "            if nums[i] < 0:\n",
    "                heapq.heappush(minHeap, nums[i])\n",
    "            if cur_sum < 0:\n",
    "                cur_min = heapq.heappop(minHeap)\n",
    "                minSum -= cur_min\n",
    "                cur_sum -= cur_min\n",
    "                time += 1\n",
    "        if cur_sum < minSum:\n",
    "            return -1 \n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Heap:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.heap = []\n",
    "\n",
    "    def _up(self, index):\n",
    "\n",
    "        while (parent:= (index+1)//2-1 )>=0:\n",
    "            if self.heap[parent]> self.heap[index]:\n",
    "                self.heap[index],self.heap[parent] = self.heap[parent],self.heap[index]\n",
    "                index =parent\n",
    "            else:\n",
    "                return \n",
    "\n",
    "    def get_small_child(self,left):\n",
    "        heap_len = len(self.heap)\n",
    "        right =  left+1\n",
    "        if right>=heap_len:\n",
    "            return left\n",
    "        return left if self.heap[left]< self.heap[right] else right\n",
    "\n",
    "    def _down(self, index):\n",
    "        heap_len = len(self.heap)\n",
    "        while (left := index*2+1)<heap_len:\n",
    "            small_child = self.get_small_child(left)\n",
    "            if self.heap[small_child]<self.heap[index]:\n",
    "                self.heap[small_child],self.heap[index] = self.heap[index],self.heap[small_child]\n",
    "                index = small_child\n",
    "            else:\n",
    "                return \n",
    "\n",
    "    def pop(self):\n",
    "        if not self.heap:\n",
    "            return None\n",
    "        \n",
    "        self.heap[0],self.heap[-1] = self.heap[-1],self.heap[0]\n",
    "        res = self.heap.pop()\n",
    "        self._down(0)\n",
    "        return res\n",
    "        \n",
    "    def push(self, value):\n",
    "        self.heap.append(value)\n",
    "        self._up(len(self.heap)-1)\n",
    "\n",
    "    \n",
    "    def __bool__(self):\n",
    "        return len(self.heap) != 0\n",
    "\n",
    "class Solution:\n",
    "    def magicTower(self, nums: List[int]) -> int:\n",
    "        surffix = []\n",
    "        heap = Heap()\n",
    "        base =1\n",
    "        for v in nums:\n",
    "            if v<0:\n",
    "                if base+v <=0:\n",
    "                    if not heap:\n",
    "                        surffix.append(v)\n",
    "                        # surffix.append(v)\n",
    "                        # base+=v\n",
    "                        continue\n",
    "                        # return -1\n",
    "                    # print(heap.heap)\n",
    "                    if heap.heap[0]>=v:\n",
    "                        surffix.append(v)\n",
    "                        # base+=v\n",
    "                        continue\n",
    "                    \n",
    "                    top = heap.heap[0]\n",
    "                    heap.heap[0] = v\n",
    "                    heap._down(0)\n",
    "                    surffix.append(top)\n",
    "                    base-= top\n",
    "                    \n",
    "                else:\n",
    "                    heap.push(v)\n",
    "            base+=v\n",
    "        for v in surffix:\n",
    "            base+=v\n",
    "            if base<=0:\n",
    "                return -1\n",
    "        # print(surffix)\n",
    "        return len(surffix)\n",
    "                \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
